/* Copyright 2011 Tobias Marschall, Email: tm@cwi.nl 
 * 
 * This file is part of string-cover.
 *
 * string-cover is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * string-cover is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with string-cover.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <limits>
#include <cmath>

#include "BoundProvider.h"

#include "BranchAndBoundSolver.h"

using namespace std;

BranchAndBoundSolver::BranchAndBoundSolver(BoundProvider& bound_provider, const BranchingRule<node_queue_t>& branching_rule) : bound_provider(bound_provider), branching_rule(branching_rule) {

}

BranchAndBoundSolver::~BranchAndBoundSolver() {
}

void BranchAndBoundSolver::setMinLength(int min_length) {
	this->min_length = min_length;
}

void BranchAndBoundSolver::setMaxLength(int max_length) {
	this->max_length = max_length;
}

std::auto_ptr<Solution> BranchAndBoundSolver::solve(const ProblemInstance& instance) {
	// pass minimal and maximal length on to the bound provider
	bound_provider.setMinLength(min_length);
	bound_provider.setMaxLength(max_length);
	// create root node of branch and bound tree
	BranchAndBoundNode* root_node = new BranchAndBoundNode(instance);

	double global_lower_bound = numeric_limits<double>::infinity();
	double* substring_weight_sums = new double[instance.getSubstrings().size()];
	auto_ptr<Solution> best_solution(0);
	if ((min_length<0) && (max_length<0)) {
		best_solution = Solution::createAllLettersSolution(instance);
		auto_ptr<Solution> trivial_solution = Solution::createAllStringsSolution(instance);
		if (trivial_solution->getScore() < best_solution->getScore()) {
			best_solution = trivial_solution;
		}
		cout << "Found trivial solution with score " << best_solution->getScore() << endl;
	}
	// auto_ptr<Solution> best_solution = bound_provider.compute_bounds(*root_node, &global_lower_bound, substring_weight_sums);

	// a queue of branching tree nodes that have to be examined
	node_queue_t node_queue;
	node_queue.push(root_node);

	// iterate until queue is empty or best solution has been found, i.e. lower and
	// upper bound meet.
	unsigned long long n = 0;
	while (node_queue.size()>0) {
		n += 1;
		if (n%status_iterations == 0) {
			cout << "Iteration " << n << endl;
			cout << "   Active branching nodes: " << node_queue.size() << endl;
			if (best_solution.get() != 0) {
				cout << "   Best score: " << best_solution->getScore() << endl;
			}
			// cout << "   Best solution: " << *best_solution << endl;
		}
		BranchAndBoundNode* node = node_queue.top();
		node_queue.pop();
		// cout << "   Current node's priority: " << node->getPriority() << endl;
#ifdef DEBUG
		cout << "--------------" << endl;
		if (node->isRoot()) cout << "At ROOT node" << endl;
		cout << *node << endl;
#endif
		double lower_bound = numeric_limits<double>::infinity();
		auto_ptr<Solution> auto_solution(0);
		if (best_solution.get() != 0) {
			auto_solution = bound_provider.compute_bounds(*node, best_solution->getScore(), &lower_bound, substring_weight_sums);
		} else {
			auto_solution = bound_provider.compute_bounds(*node, numeric_limits<double>::infinity(), &lower_bound, substring_weight_sums);
		}
		Solution* solution = auto_solution.get();
		if (solution == 0) {
#ifdef DEBUG
			cout << "No solution possible with the constraints of current b&b node." << endl;
#endif
			if (node->isRoot()) {
				delete node;
				return auto_ptr<Solution>(0);
			}
			delete node;
			continue;
		}
#ifdef DEBUG
		cout << "Node: " << *node << endl;
		cout << "   Node's Lower Bound: " << lower_bound << endl;
#endif
		if (instance.hasIntegerWeights()) {
			lower_bound = ceil(lower_bound-1e-10);
		}
		if ((best_solution.get()==0) || (best_solution->getScore() > solution->getScore())) {
			best_solution = auto_solution;
#ifdef DEBUG
			cout << "Found new best solution." << endl;
#endif
		}
		if (node->isRoot()) {
			global_lower_bound = lower_bound;
			cout << "Root node: lower bound: " << global_lower_bound << ", upper bound: " << best_solution->getScore() << endl;
		}
#ifdef DEBUG
		cout << "Best solution: " << best_solution->getScore() << endl;
		cout << "Local lower bound: " << lower_bound << ", local feasible solution (score "<< solution->getScore() << "): "<< *solution << endl;
#endif
		// cout << "   Local lower bound: " << lower_bound << endl;
		// check whether optimal solution has been found
		if (fabs(1.0-global_lower_bound/solution->getScore()) < 1e-10) {
			delete node;
			break;
		}
		// check whether we can prune this branch
		if (best_solution->getScore() <= lower_bound) {
#ifdef DEBUG
			cout << "Lower bound is not better than best known solution: pruning search tree" << endl;
#endif
			delete node;
			continue;
		}
		// if there is a gap between lower and upper bound, then branch
		if (fabs(1.0-lower_bound/solution->getScore()) >= 1e-10) {
			branching_rule.branch(node_queue, *node, lower_bound, *solution, substring_weight_sums);
		}
		delete node;
	}
	delete[] substring_weight_sums;
	// free all left-over nodes
	while (node_queue.size()>0) {
		BranchAndBoundNode* node = node_queue.top();
		node_queue.pop();
		delete node;
	}
	cout << "Found optimal solution in " << n << " iterations" << endl;
	return best_solution;
}

void BranchAndBoundSolver::setStatusIterations(int iterations) {
	this->status_iterations = iterations;
}






